import operator,copy
from numbertheory import Fraction



def solve_linear_equations(co_matrix,value_matrix):
    if len(value_matrix[0])!=1:
        raise ValueError("Value Matrix must have only one column.")
    
    cp_values = copy.deepcopy(value_matrix)
    Matrix._solve(co_matrix,cp_values)
    return map(lambda line:line[0],cp_values)

#############seperate line################
class Matrix:
    
    def __init__(self,matrix):
        self.matrix = copy.deepcopy(matrix)

    def transpose(self):
        m,n = len(self.matrix[0]),len(self.matrix)
        return Matrix([[ self.matrix[j][i] for j in xrange(n)] for i in xrange(m)])

    def determinat():
        #todo
        pass

    def is_invertible(self):
        return determinat() != 0
    
    def __add__(self,other):
        return self._merge(other,operator.add)

    def __sub__(self,other):
        return self._merge(other,operator.sub)

    def __mul__(self,other):
        m1,m2 = len(self.matrix),len(other)
        n1,n2 = len(self.matrix[0]),len(other.matrix[0])
        if n1 != m2 :
            raise ValueError("Can't multiplicate %dx%d matrix to %dx%d matrix")

        m,n = m1,n2
        return Matrix([[sum([self.matrix[i][x]*other.matrix[x][j] for x in xrange(n1)])
                        for j in xrange(n)] for i in xrange(m)])

    def __invert__(self):
        imatrix = Matrix._indentity(len(self))
        Matrix._solve(self.matrix,imatrix)
        return imatrix

    def __eq__(self,other):
        return self.matrix == other.matrix
    
    def __getitem__(self,key):
        return self.matrix[key]

    def __setitem__(self,key,value):
        self.matrix[key] = value

    def __iter__(self):
        return iter(self.matrix)

    def __len__(self):
        return len(self.matrix)
    
    def __repr__(self):
        str_buff = []
        for line in self.matrix:
            str_buff.append(str(line))
            str_buff.append("\n")
        return "".join(str_buff)

    def solve(self,value_matrix):
        return solve_line_equations(self,value_matrix)
        

    @staticmethod
    def _scale_line(dest_line,ce):
        for j in xrange(len(dest_line)):
            dest_line[j]*=ce
            
    @staticmethod
    def _eliminate_line(dest_line,dest_c,src_line,src_c):
        for j in range(len(src_line)):
            dest_line[j] = (dest_c*dest_line[j]- src_c*src_line[j])
            
    @staticmethod
    def _indentity(size):
        zero_m = [[0 for j in range(size)] for i in range(size)]
        for i in range(size):
            zero_m[i][i] = 1
        return Matrix(zero_m)

    @staticmethod
    def _solve(src_matrix,*comatrixs):
        m,n = len(src_matrix),len(src_matrix[0])
        if m!=n:
            raise ValueError("Can't invert a non-square matrix")

        to_inv = copy.deepcopy(src_matrix)
        
        #traverse the trianlge line
        for t in range(m):
            #eliminate the coefficient of the other rows
            for i in range(m):
                if i == t or to_inv[i][t] == 0:
                    continue
                
                src_c ,dest_c = to_inv[i][t],to_inv[t][t]
                Matrix._eliminate_line(to_inv[i],dest_c,to_inv[t],src_c)

                #do the same operation on the comatrixs
                for comatrix in comatrixs:
                    Matrix._eliminate_line(comatrix[i],dest_c,comatrix[t],src_c)
                
        
        for t in range(m):
            for comatrix in comatrixs:
                Matrix._scale_line(comatrix[t],1/to_inv[t][t])


    
    def _merge(self,other,operand):
        m1,m2 =  len(self.matrix) , len(other.matrix)
        n1,n2 = len(self[0]) , len(other[0])
        if m1!=m2 or n1!=n2:
            raise ValueError("Can't %s a %dx%d matrix to %dx%d matrix."
                             %(operand.__name__,m1,n1,m2,n2))
        
        return Matrix(map(lambda l1,l2:map(operand,l1,l2),self,other))
